package com.buaa.leecode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Convert Sorted Array to Binary Search Tree
 */
public class N109 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    int count = 0;

    private void bfsTreeNode(LinkedList<TreeNode> queue) {
        if (queue.isEmpty()) {
            return;
        }
        TreeNode top = queue.poll();
        System.out.print("," + top.val);
        int flag = 0;
        if (top.left != null) {
            queue.add(top.left);
            flag++;
        }
        if (top.right != null) {
            queue.add(top.right);
            flag++;
        }
        if (flag == 1) {
//            System.out.print(",null");
        }
        bfsTreeNode(queue);
    }

    private void scanInput(ListNode head, ArrayList<Integer> arr) {
        while (head != null) {
            arr.add(head.val);
            head = head.next;
        }
    }

    private void print(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        bfsTreeNode(queue);
    }

    private ListNode cutMiddle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null;
        ListNode next = head;
        while (next.next != null) {
            next = next.next;
            if (next.next != null) {
                pre = head;
                head = head.next;
                next = next.next;
            }
        }
        if (pre != null) {
            pre.next = null;
        }
        return head;
    }


    private void print(ListNode head) {
        while (head != null) {
            System.out.print("," + head.val);
            head = head.next;
        }
        System.out.println("");
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        print(head);
        ListNode middle = cutMiddle(head);
        if (middle == null) {
            return null;
        }
        System.out.println(count + "=> 取中间数：" + middle.val);
        count++;
        TreeNode node = new TreeNode(middle.val);
        if (middle != head) {
            node.left = sortedListToBST(head);
        }
        node.right = sortedListToBST(middle.next);
        return node;
    }

    private ListNode buildList(int[] nums) {
        ListNode head = null, tail = null;
        for (int i = 0; i < nums.length; i++) {
            if (head == null) {
                tail = head = new ListNode(nums[i]);
            } else {
                tail.next = new ListNode(nums[i]);
                tail = tail.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        int[] nums = {-10, -3, 0, 5, 9};
        N109 solution = new N109();
        ListNode root = solution.buildList(nums);
        TreeNode ans = solution.sortedListToBST(root);
        solution.print(ans);
    }

}
